package algorithm.dynamic_programming;

public class Knapsack {

    public static int getMaxValue(int[] w, int[] v, int bag){
        return process(w, v, bag, 0, 0);
    }

    public static int process(int[] w, int[] v, int bag, int alreadyW, int index){
        if(alreadyW > bag){
            return -1;
        }
        if(index == w.length){
            return 0;
        }
        int res1 = process(w, v, bag, alreadyW, index + 1);
        int res2 = process(w, v, bag, alreadyW + w[index], index + 1);
        if (res2 != -1) {
            return Math.max(res2 + v[index], res1);
        } else {
            return res1;
        }
    }

    public static int getMaxValue2(int[] w, int[] v, int bag){
        return process3(w, v, bag, 0);
    }

    public static int process2(int[] w, int[] v, int rest, int index) {
        if (rest < 0)
            return -1;
        if (index == w.length)
            return 0;
        int res1 = process2(w, v, rest, index + 1);
        int res2 = process2(w, v, rest - w[index], index + 1);
        if (res2 != -1) {
            return Math.max(res2 + v[index], res1);
        } else {
            return res1;
        }
    }

    public static int process3(int[] w, int[] v, int rest, int index) {
        if (index == w.length)
            return 0;
        int res1 = process2(w, v, rest, index + 1);
        int res2 = 0;
        if (res2 - w[index] >= 0) {
            res2 = process2(w, v, rest - w[index], index + 1) + v[index];
        }
        return Math.max(res2, res1);
    }

    public static void main(String[] args) {
        int[] weights = { 3, 2, 4, 7 };
        int[] values = { 5, 6, 3, 19 };
        int bag = 11;
        System.out.println(getMaxValue2(weights, values, bag));
    }
}
